package org.laizili.solution.codinginterviews;

import java.util.*;

/**
 * <a href="https://leetcode.cn/problems/Jf1JuT/">剑指 Offer II 114. 外星文字典</a>
 * <p>
 * tags: 图的应用; 邻接表; 拓扑排序;
 * <p>
 * notes: <b>字典序</b> 理解
 * <ol>
 * <li>比较字符串a,b第一个不相等的字符的大小</li>
 * <li>比较字符串a,b的长度大小</li>
 * </ol>
 */
public class Problem114 {
    private static class Solution {
        private static final int TABLE_LENGTH = 26;

        public String alienOrder(String[] words) {
            if (words.length == 1) {
                return words[0];
            }
            // 有向图邻接表
            List[] verArcs = new List[TABLE_LENGTH];
            int[] inDegree = new int[TABLE_LENGTH];
            Set<Integer> vertices = new HashSet<>();
            boolean initialized = initialize(words, vertices, verArcs, inDegree);
            if (initialized) {
                StringBuilder charOrder = new StringBuilder(26);
                Deque<Integer> stack = new ArrayDeque<>();
                for (Integer vertex : vertices) {
                    if (inDegree[vertex] == 0) {
                        stack.push(vertex);
                    }
                }
                while (!stack.isEmpty()) {
                    int vertex = stack.pop();
                    charOrder.append((char) (vertex + 'a'));
                    List<Integer> arcVets = verArcs[vertex];
                    if (arcVets != null) {
                        for (int arcV : arcVets) {
                            if (inDegree[arcV] > 0) {
                                if (--inDegree[arcV] == 0) {
                                    stack.push(arcV);
                                }
                            }
                        }
                    }
                }
                if (charOrder.length() == vertices.size()) {
                    return charOrder.toString();
                } else
                    return "";
            }
            return "";
        }

        private boolean initialize(String[] words, Set<Integer> vertices, List[] map, int[] inDegree) {
            for (String word : words) {
                int len = word.length();
                for (int i = 0; i < len; i++) {
                    vertices.add(word.charAt(i) - 'a');
                }
            }
            String left = words[0];
            String right;
            char chL, chR;
            int idL, idR;
            for (int i = 1; i < words.length; i++) {
                right = words[i];
                int leftLength = left.length();
                int rightLength = right.length();
                int min = Math.min(leftLength, rightLength);
                int k;
                boolean cmpContinued = true;
                for (k = 0; k < min; k++) {
                    chL = left.charAt(k);
                    chR = right.charAt(k);
                    idL = chL - 'a';
                    if (chL != chR) {
                        cmpContinued = false;
                        idR = chR - 'a';
                        if (map[idL] == null) {
                            map[idL] = new ArrayList<>();
                        }
                        map[idL].add(idR);
                        inDegree[idR]++;
                        break;
                    }
                }
                if (cmpContinued) {
                    if (leftLength > rightLength) {
                        // 不合法的字典序
                        return false;
                    }
                }
                left = right;
            }
            return true;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().alienOrder(new String[]{"abcf", "abc"}));
    }
}
